package com.dh.leetcode.k1;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @ClassName: _1370_Increasing_decreasing_string
 * @Description: 1370. 上升下降字符串
 * <p>
 * https://leetcode-cn.com/problems/increasing-decreasing-string/
 * <p>
 * 给你一个字符串 s ，请你根据下面的算法重新构造字符串：
 * <p>
 * 从 s 中选出 最小 的字符，将它 接在 结果字符串的后面。
 * 从 s 剩余字符中选出 最小 的字符，且该字符比上一个添加的字符大，将它 接在 结果字符串后面。
 * 重复步骤 2 ，直到你没法从 s 中选择字符。
 * 从 s 中选出 最大 的字符，将它 接在 结果字符串的后面。
 * 从 s 剩余字符中选出 最大 的字符，且该字符比上一个添加的字符小，将它 接在 结果字符串后面。
 * 重复步骤 5 ，直到你没法从 s 中选择字符。
 * 重复步骤 1 到 6 ，直到 s 中所有字符都已经被选过。
 * 在任何一步中，如果最小或者最大字符不止一个 ，你可以选择其中任意一个，并将其添加到结果字符串。
 * <p>
 * 请你返回将 s 中字符重新排序后的 结果字符串 。
 * @Author: shouzimu
 * @Date: 2020/11/25 10:46
 */
public class _1370_Increasing_decreasing_string {

    /**
     * 使用桶排序，题目中给定都为小写字母
     *
     * @param s
     * @return
     */
    public String sortString(String s) {
        char[] array = s.toCharArray();
        int len = 26;
        int[] bucket = new int[len];
        for (char c : array) {
            bucket[c - 'a']++;
        }
        StringBuilder builder = new StringBuilder();

        do {
            for (int i = 0; i < len; i++) {
                if (bucket[i] != 0) {
                    builder.append((char) ('a' + i));
                    bucket[i]--;
                }
            }
            for (int i = len - 1; i >= 0; i--) {
                if (bucket[i] != 0) {
                    builder.append((char) ('a' + i));
                    bucket[i]--;
                }
            }
        } while (builder.length() < s.length());
        return builder.toString();
    }

    /**
     * 第一版实现，有点屎了
     * 看了大佬们和官方的实现，使用的是桶排序
     *
     * @param s
     * @return
     */
    public String sortString_first(String s) {
        char[] array = s.toCharArray();
        Arrays.sort(array);
        //转成List + 栈的结构
        List<Stack<Character>> list = new ArrayList<>();
        char prev = array[0];
        Stack<Character> prevStack = new Stack<>();
        for (char c : array) {
            if (c != prev) {
                prev = c;
                list.add(prevStack);
                prevStack = new Stack<>();
            }
            prevStack.push(c);
        }
        list.add(prevStack);

        StringBuilder res = new StringBuilder();

        while (true) {
            boolean allEmpty = true;
            for (int i = 0; i < list.size(); i++) {
                Stack st = list.get(i);
                if (!st.isEmpty()) {
                    res.append(st.pop());
                    allEmpty = false;
                }
            }
            for (int i = list.size() - 1; i >= 0; i--) {
                Stack st = list.get(i);
                if (!st.isEmpty()) {
                    res.append(st.pop());
                    allEmpty = false;
                }
            }
            if (allEmpty) {
                break;
            }
        }

        return res.toString();
    }

    @Test
    public void sortStringTest() {
        String s = "aaaabbbbcccc";
        Assert.assertEquals("abccbaabccba", sortString(s));

        s = "rat";
        Assert.assertEquals("art", sortString(s));
        s = "leetcode";
        Assert.assertEquals("cdelotee", sortString(s));
    }
}
